// LRU 缓存

package Leetcode;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

class LRUCache {
    public int capacity;
    public Map<Integer, Integer> map = new HashMap<>();
    public Deque<Integer> deque = new LinkedList<>(); // 最开始的是最近最久未使用

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            // 删除这个数并且放在最后表示最近使用
            deque.remove(key);
            deque.addLast(key);

            return map.get(key);
        }
        return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.remove(key);
            map.put(key, value);
            // 将其放到队尾
            deque.remove(key);
            deque.addLast(key);
        } else {
            if (map.size() < capacity) {
                map.put(key, value);
                deque.addLast(key);
            } else if (map.size() == capacity) {
                // 删除最久未使用的元素
                int r = deque.pop();
                map.remove(r);
                // 添加新的元素
                map.put(key, value);
                deque.addLast(key);
            }
        }
    }
}